package leetcode_top;

import tree.TreeNode;

public class Ex108 {
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            // TreeNode root = null;
            // for (int i = 0; i < nums.length; i++) {
            //     root = makeTree(root, nums[i]);
            // }
            // return root;
            return preOrder(0, nums.length - 1, nums);
        }

        public TreeNode makeTree(TreeNode root, int val) { 
            if (root == null) {
                return new TreeNode(val);
            }
            if (val <= root.val) {
                root.left = makeTree(root.left, val);
            } else {
                root.right = makeTree(root.right, val);
            }
            return root;
        }

        public TreeNode preOrder(int lo, int hi, int[] nums) { 
            if (lo > hi) return null;
            if (lo == hi) return new TreeNode(nums[lo]);
            int r = (hi - lo) / 2 + lo;
            TreeNode root = new TreeNode(nums[r]);
            root.left = preOrder(lo, r - 1, nums);
            root.right = preOrder(r + 1, hi, nums);
            return root;
        }
    }
}
